﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Sol543
{
    int res = 0;
    public int DiameterOfBinaryTree(TreeNode root)
    {
        //父亲的等于两个孩子节点返回的最大的深度，而不是孩子的最大路径

        DepthTree(root);



        return res - 1;
    }
    public int DepthTree(TreeNode root)//计算层数h？
    {
        
        if (root == null) return 0;

        int leftdepth = DepthTree(root.left);
        int rightdepth = DepthTree(root.right);

        int depth = Math.Max(leftdepth, rightdepth)+1;
        res = Math.Max(leftdepth+ rightdepth+1, res);

        return depth;
    }

}

public class Solution543_2
{
    int maxLen = 0;
    //思路，就是根结点左边的直径加上右边的直径
    public int DiameterOfBinaryTree(TreeNode root)
    {

        //先遍历所有的根节点，计算每个点的长度

        //先序遍历吧
        PreOredr(root);
        return maxLen;

    }

    private void PreOredr(TreeNode root)//中左右
    {if(root == null) return;


        
        //操作一下
        int len=GetLen(root.left)+ GetLen(root.right);
        maxLen= Math.Max(len, maxLen);
        Console.WriteLine("root:  " + root.val+ "   len:   " + len);
      
        PreOredr(root.left);
        PreOredr(root.right);
    }

    private int GetLen(TreeNode root)//计算这个根到叶子结点的路径长度
    {
        if(root == null) return 0;

        return Math.Max( GetLen(root.left) , GetLen(root.right))+1;

    }
}

class Program543
{


    static void Main543(string[] args)
    {
        int[] preOrder = { 1, 2,4,5, 3 };
        int[] inOrder = { 4,2,5,1,3 };

        Solution105 Solution105 = new Solution105();
        TreeNode root = Solution105.BuildTree(preOrder, inOrder);


        //Solution105.levelOrder(root);
        //Sol543 sol= new ();
        Solution543_2 sol = new ();
        int res= sol.DiameterOfBinaryTree(root);    
        Console.WriteLine(res);

    }
}